SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Maximum flow problem</title>

</head>

Maximum flow problem

</h1>

</header>

In <a href="Optimization_(mathematics)" class="mw-redirect" title="Optimization (mathematics)">optimization theory</a>, maximum flow problems involve finding a feasible flow through a <a href="Flow_network" title="Flow network">flow network</a> that obtains the maximum possible flow rate.

The maximum flow problem can be seen as a special case of more <a href="Complex_network" title="Complex network">complex network</a> flow problems, such as the <a href="Circulation_problem" title="Circulation problem">circulation problem</a>. The maximum value of an s-t flow (i.e., flow from <a href="Glossary_of_graph_theory#Direction" title="Glossary of graph theory">source</a> s to <a href="Glossary_of_graph_theory#Direction" title="Glossary of graph theory">sink</a> t) is equal to the minimum capacity of an <a href="Cut_(graph_theory)" title="Cut (graph theory)">s-t cut</a> (i.e., cut severing s from t) in the network, as stated in the <a href="Max-flow_min-cut_theorem" title="Max-flow min-cut theorem">max-flow min-cut theorem</a>.

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

The maximum flow problem was first formulated in 1954 by <a href="Ted_Harris_(mathematician)" title="Ted Harris (mathematician)">T. E. Harris</a> and F. S. Ross as a simplified model of Soviet railway traffic flow.<a href="#cite_note-:0-1">[1]</a><a href="#cite_note-2">[2]</a><a href="#cite_note-:2-3">[3]</a>

In 1955, <a href="Lester_R._Ford%2C_Jr." class="mw-redirect" title="Lester R. Ford, Jr.">Lester R. Ford, Jr.</a> and <a href="D._R._Fulkerson" title="D. R. Fulkerson">Delbert R. Fulkerson</a> created the first known algorithm, the <a href="Ford%E2%80%93Fulkerson_algorithm" title="Ford–Fulkerson algorithm">Ford–Fulkerson algorithm</a>.<a href="#cite_note-:1-4">[4]</a><a href="#cite_note-:3-5">[5]</a> In their 1955 paper,<a href="#cite_note-:1-4">[4]</a> Ford and Fulkerson wrote that the problem of Harris and Ross is formulated as follows (see<a href="#cite_note-:0-1">[1]</a> p. 5):<blockquote>Consider a rail network connecting two cities by way of a number of intermediate cities, where each link of the network has a number assigned to it representing its capacity. Assuming a steady state condition, find a maximal flow from one given city to the other.</blockquote>In their book Flows in Networks,<a href="#cite_note-:3-5">[5]</a> in 1962, Ford and Fulkerson wrote:<blockquote>It was posed to the authors in the spring of 1955 by T. E. Harris, who, in conjunction with General F. S. Ross (Ret.), had formulated a simplified model of railway traffic flow, and pinpointed this particular problem as the central one suggested by the model [11].</blockquote>where [11] refers to the 1955 secret report Fundamentals of a Method for Evaluating Rail net Capacities by Harris and Ross<a href="#cite_note-:2-3">[3]</a> (see<a href="#cite_note-:0-1">[1]</a> p. 5).

Over the years, various improved solutions to the maximum flow problem were discovered, notably the shortest augmenting path algorithm of Edmonds and Karp and independently Dinitz; the blocking flow algorithm of Dinitz; the <a href="Push%E2%80%93relabel_maximum_flow_algorithm" title="Push–relabel maximum flow algorithm">push-relabel algorithm</a> of <a href="Andrew_V._Goldberg" title="Andrew V. Goldberg">Goldberg</a> and <a href="Robert_Tarjan" title="Robert Tarjan">Tarjan</a>; and the binary blocking flow algorithm of Goldberg and Rao. The algorithms of Sherman<a href="#cite_note-6">[6]</a> and Kelner, Lee, Orecchia and Sidford,<a href="#cite_note-7">[7]</a><a href="#cite_note-8">[8]</a> respectively, find an approximately optimal maximum flow but only work in undirected graphs.

In 2013 <a href="James_B._Orlin" title="James B. Orlin">James B. Orlin</a> published a paper describing an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|V||E|)}">

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|V||E|)}</annotation>

</semantics>

</math><img src="./2d81aded51fae699d4f659fee1faa684233ab581.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.733ex; height:2.843ex;" alt="{\displaystyle O(|V||E|)}" loading="lazy"> algorithm.<a href="#cite_note-orlin-9">[9]</a>

In 2022 Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva published an almost-linear time algorithm running in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|E|^{1+o(1)})}">

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|E|^{1+o(1)})}</annotation>

</semantics>

</math><img src="./8979f5c33dbfc37920b6196e1e73efedadc7b0c1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.883ex; height:3.509ex;" alt="{\displaystyle O(|E|^{1+o(1)})}" loading="lazy"> for the <a href="Minimum-cost_flow_problem" title="Minimum-cost flow problem">minimum-cost flow</a> problem of which for the maximum flow problem is a particular case.<a href="#cite_note-almost_linear-10">[10]</a><a href="#cite_note-11">[11]</a> For the <a href="Single_source_shortest_path_problem" class="mw-redirect" title="Single source shortest path problem">single-source shortest path (SSSP) problem</a> with negative weights another particular case of minimum-cost flow problem an algorithm in almost-linear time has also been reported.<a href="#cite_note-12">[12]</a><a href="#cite_note-13">[13]</a> Both algorithms were deemed best papers at the 2022 <a href="Symposium_on_Foundations_of_Computer_Science" title="Symposium on Foundations of Computer Science">Symposium on Foundations of Computer Science</a>.<a href="#cite_note-14">[14]</a><a href="#cite_note-15">[15]</a>

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

First we establish some notation:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N=(V,E)}</annotation>

</semantics>

</math><img src="./07d84a414272337c9fc13d80b15a4b77e01b84a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.568ex; height:2.843ex;" alt="{\displaystyle N=(V,E)}" loading="lazy"> be a flow network with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s,t\in V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s,t\in V}</annotation>

</semantics>

</math><img src="./9f1f09701bea7d83d020d74ffd3232663134d098.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.592ex; height:2.509ex;" alt="{\displaystyle s,t\in V}" loading="lazy"> being the source and the sink of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> respectively.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy"> is a function on the edges of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> then its value on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (u,v)\in E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (u,v)\in E}</annotation>

</semantics>

</math><img src="./fb3670c33f5481059c095a58c9ebbd60dc6f35f8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.917ex; height:2.843ex;" alt="{\displaystyle (u,v)\in E}" loading="lazy"> is denoted by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{uv}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g_{uv}}</annotation>

</semantics>

</math><img src="./5a8ee98d3e96cd8ec8f92c096975535e5aefd24b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.079ex; height:2.009ex;" alt="{\displaystyle g_{uv}}" loading="lazy"> or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(u,v).}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(u,v).}</annotation>

</semantics>

</math><img src="./5614c256eadb6abf7d12783d9e5d01ae8bf6ac2d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.063ex; height:2.843ex;" alt="{\displaystyle g(u,v).}" loading="lazy"></li></ul>

Definition. The capacity of an edge is the maximum amount of flow that can pass through an edge. Formally it is a map <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c:E\to \mathbb {R} ^{+}.}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c:E\to \mathbb {R} ^{+}.}</annotation>

</semantics>

</math><img src="./64e5681930034379038263547fe56bcb96180818.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:12.169ex; height:2.509ex;" alt="{\displaystyle c:E\to \mathbb {R} ^{+}.}" loading="lazy">

Definition. A flow is a map <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:E\to \mathbb {R} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f:E\to \mathbb {R} }</annotation>

</semantics>

</math><img src="./3476ca7d92ca2b5782c4d0570eaa04f89608ee1c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.284ex; height:2.509ex;" alt="{\displaystyle f:E\to \mathbb {R} }" loading="lazy"> that satisfies the following:

<ul><li>Capacity constraint. The flow of an edge cannot exceed its capacity, in other words: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{uv}\leq c_{uv}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{uv}\leq c_{uv}}</annotation>

</semantics>

</math><img src="./b5280479bf4c751c7a708901ae8a877dddf56bf7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.184ex; height:2.509ex;" alt="{\displaystyle f_{uv}\leq c_{uv}}" loading="lazy"> for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (u,v)\in E.}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (u,v)\in E.}</annotation>

</semantics>

</math><img src="./0d6e9c262c62f1a0dbf6ac3ff54ceac0c7b32a06.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.564ex; height:2.843ex;" alt="{\displaystyle (u,v)\in E.}" loading="lazy"></li>

<li>Conservation of flows. The sum of the flows entering a node must equal the sum of the flows exiting that node, except for the source and the sink. Or:</li></ul>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \forall v\in V\setminus \{s,t\}:\quad \sum _{u:(u,v)\in E,f_{uv}>0}f_{uv}=\sum _{u:(v,u)\in E,f_{vu}>0}f_{vu}.}</annotation>

</semantics>

</math><img src="./b7c776c21d6a97f7f780048a775a29b7b3e0aac5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:53.853ex; height:6.009ex;" alt="{\displaystyle \forall v\in V\setminus \{s,t\}:\quad \sum _{u:(u,v)\in E,f_{uv}>0}f_{uv}=\sum _{u:(v,u)\in E,f_{vu}>0}f_{vu}.}" loading="lazy"></dd></dl></dd></dl>

Remark. Flows are skew symmetric: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{uv}=-f_{vu}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{uv}=-f_{vu}}</annotation>

</semantics>

</math><img src="./57af4d8537ee892330f4fdcdeb91623bff33f441.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.125ex; height:2.509ex;" alt="{\displaystyle f_{uv}=-f_{vu}}" loading="lazy"> for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (u,v)\in E.}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (u,v)\in E.}</annotation>

</semantics>

</math><img src="./0d6e9c262c62f1a0dbf6ac3ff54ceac0c7b32a06.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.564ex; height:2.843ex;" alt="{\displaystyle (u,v)\in E.}" loading="lazy">

Definition. The value of flow is the amount of flow passing from the source to the sink. Formally for a flow <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:E\to \mathbb {R} ^{+}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f:E\to \mathbb {R} ^{+}}</annotation>

</semantics>

</math><img src="./31b8586bcf5071c6a854e2c20a3c424721707dee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.794ex; height:2.843ex;" alt="{\displaystyle f:E\to \mathbb {R} ^{+}}" loading="lazy"> it is given by:

</mrow>

</mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |f|=\sum _{v:\ (s,v)\in E}f_{sv}=\sum _{u:\ (u,t)\in E}f_{ut}.}</annotation>

</semantics>

</math><img src="./67cfd9d536875af8c5702cfd066f8f896b2fc640.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:31.129ex; height:6.009ex;" alt="{\displaystyle |f|=\sum _{v:\ (s,v)\in E}f_{sv}=\sum _{u:\ (u,t)\in E}f_{ut}.}" loading="lazy"></dd></dl>

Definition. The maximum flow problem is to route as much flow as possible from the source to the sink, in other words find the flow <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{\textrm {max}}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{\textrm {max}}}</annotation>

</semantics>

</math><img src="./abd7767827e2c1e9e04af86a7c0d8aa65def28ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.43ex; height:2.509ex;" alt="{\displaystyle f_{\textrm {max}}}" loading="lazy"> with maximum value.

Note that several maximum flows may exist, and if arbitrary real (or even arbitrary rational) values of flow are permitted (instead of just integers), there is either exactly one maximum flow, or infinitely many, since there are infinitely many linear combinations of the base maximum flows. In other words, if we send <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> units of flow on edge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u}</annotation>

</semantics>

</math><img src="./c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" loading="lazy"> in one maximum flow, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y>x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y>x}</annotation>

</semantics>

</math><img src="./a22112f92b4b6d0c2f20283a6b5cb93e384091ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.584ex; height:2.176ex;" alt="{\displaystyle y>x}" loading="lazy"> units of flow on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u}</annotation>

</semantics>

</math><img src="./c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" loading="lazy"> in another maximum flow, then for each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Delta \in [0,y-x]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta \in [0,y-x]}</annotation>

</semantics>

</math><img src="./b41089fba26fd70281e24a3bfb108362ef7a908a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.592ex; height:2.843ex;" alt="{\displaystyle \Delta \in [0,y-x]}" loading="lazy"> we can send <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x+\Delta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x+\Delta }</annotation>

</semantics>

</math><img src="./6013b05e56008ae2e0b19fa62dcc5a1a1707a90f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.106ex; height:2.343ex;" alt="{\displaystyle x+\Delta }" loading="lazy"> units on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u}</annotation>

</semantics>

</math><img src="./c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" loading="lazy"> and route the flow on remaining edges accordingly, to obtain another maximum flow. If flow values can be any real or rational numbers, then there are infinitely many such <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Delta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta }</annotation>

</semantics>

</math><img src="./32769037c408874e1890f77554c65f39c523ebe2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.936ex; height:2.176ex;" alt="{\displaystyle \Delta }" loading="lazy"> values for each pair <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x,y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x,y}</annotation>

</semantics>

</math><img src="./5ea0abffd33a692ded22accc104515a032851dff.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.519ex; height:2.009ex;" alt="{\displaystyle x,y}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Algorithms">Algorithms</h2></div>

The following table lists algorithms for solving the maximum flow problem.

Here, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math><img src="./4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"> denote the number of vertices and edges of the network.

The value <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U}</annotation>

</semantics>

</math><img src="./458a728f53b9a0274f059cd695e067c430956025.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.783ex; height:2.176ex;" alt="{\displaystyle U}" loading="lazy"> refers to the largest edge capacity after rescaling all capacities to integer values

(if the network contains <a href="Irrational_number" title="Irrational number">irrational</a> capacities, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U}</annotation>

</semantics>

</math><img src="./458a728f53b9a0274f059cd695e067c430956025.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.783ex; height:2.176ex;" alt="{\displaystyle U}" loading="lazy"> may be infinite).

<th>Method

</th>

<th>Year

</th>

<th>Complexity

</th>

<th>Description

</th></tr>

<tr>

<td><a href="Linear_programming" title="Linear programming">Linear programming</a>

</td>

<td>

</td>

<td>

</td>

<td>Constraints given by the definition of a <a href="Flow_network" title="Flow network">legal flow</a>. See the <a href="Max-flow_min-cut_theorem#Linear_program_formulation" title="Max-flow min-cut theorem">linear program</a> here.

</td></tr>

<tr>

<td><a href="Ford%E2%80%93Fulkerson_algorithm" title="Ford–Fulkerson algorithm">Ford–Fulkerson algorithm</a>

</td>

<td>1955

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(EU)}</annotation>

</semantics>

</math><img src="./9457ae0d026f8902f435037312b3670ac8ce53d1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.141ex; height:2.843ex;" alt="{\displaystyle O(EU)}" loading="lazy">

</td>

<td>As long as there is an open path through the residual graph, send the minimum of the residual capacities on that path.

</td></tr>

<tr>

<td><a href="Edmonds%E2%80%93Karp_algorithm" title="Edmonds–Karp algorithm">Edmonds–Karp algorithm</a>

</td>

<td>1970

</td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(VE^{2})}</annotation>

</semantics>

</math><img src="./11a040ec69aefbb3d561b989787d5baf5e9f22bd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.218ex; height:3.176ex;" alt="{\displaystyle O(VE^{2})}" loading="lazy">

</td>

<td>A specialization of Ford–Fulkerson, finding augmenting paths with <a href="Breadth-first_search" title="Breadth-first search">breadth-first search</a>.

</td></tr>

<tr>

<td><a href="Dinic's_algorithm" title="Dinic's algorithm">Dinic's algorithm</a>

</td>

<td>1970

</td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(V^{2}E)}</annotation>

</semantics>

</math><img src="./7edf8b23e2ba797ea75ebe290d8f580b60cb0c3a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.329ex; height:3.176ex;" alt="{\displaystyle O(V^{2}E)}" loading="lazy">

</td>

<td>In each phase the algorithms builds a layered graph with <a href="Breadth-first_search" title="Breadth-first search">breadth-first search</a> on the <a href="Residual_graph" class="mw-redirect" title="Residual graph">residual graph</a>. The maximum flow in a layered graph can be calculated in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(VE)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(VE)}</annotation>

</semantics>

</math><img src="./60c9aa966bee3a2a9bfe780f23fd724dfb528bbd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.145ex; height:2.843ex;" alt="{\displaystyle O(VE)}" loading="lazy"> time, and the maximum number of phases is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V-1}</annotation>

</semantics>

</math><img src="./cf99922c8908cda9655d87b4a60c0cf3923e0e12.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.79ex; height:2.343ex;" alt="{\displaystyle V-1}" loading="lazy">. In networks with unit capacities, Dinic's algorithm terminates in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\min\{V^{2/3},E^{1/2}\}E)}">

<msup>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\min\{V^{2/3},E^{1/2}\}E)}</annotation>

</semantics>

</math><img src="./65763dbadc899d9eeef2ddc69bcbddc4b4ac2428.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.7ex; height:3.343ex;" alt="{\displaystyle O(\min\{V^{2/3},E^{1/2}\}E)}" loading="lazy"> time.

</td></tr>

<tr>

<td>MKM (Malhotra, Kumar, Maheshwari) algorithm<a href="#cite_note-16">[16]</a>

</td>

<td>1978

</td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(V^{3})}</annotation>

</semantics>

</math><img src="./6d79dfa438ce6a2035c8fab4878e8687ea6106c9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.554ex; height:3.176ex;" alt="{\displaystyle O(V^{3})}" loading="lazy">

</td>

<td>A modification of Dinic's algorithm with a different approach to constructing blocking flows. Refer to the <a href="#CITEREFMalhotraKumarMaheshwari1978">original paper</a>.

</td></tr>

<tr>

<td><a href="Dinic's_algorithm" title="Dinic's algorithm">Dinic's algorithm</a> with dynamic trees

</td>

<td>1983

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(VE\log V)}</annotation>

</semantics>

</math><img src="./ea1d30d0e4b11cfcb0265329e75fc789fe295fcc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.679ex; height:2.843ex;" alt="{\displaystyle O(VE\log V)}" loading="lazy">

</td>

<td>The <a href="Dynamic_trees" class="mw-redirect" title="Dynamic trees">dynamic trees</a> data structure speeds up the maximum flow computation in the layered graph to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(VE\log V)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(VE\log V)}</annotation>

</semantics>

</math><img src="./ea1d30d0e4b11cfcb0265329e75fc789fe295fcc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.679ex; height:2.843ex;" alt="{\displaystyle O(VE\log V)}" loading="lazy">.

</td></tr>

<tr>

<td>General <a href="Push%E2%80%93relabel_algorithm" class="mw-redirect" title="Push–relabel algorithm">push–relabel algorithm</a><a href="#cite_note-goldberg1988-17">[17]</a>

</td>

<td>1986

</td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(V^{2}E)}</annotation>

</semantics>

</math><img src="./7edf8b23e2ba797ea75ebe290d8f580b60cb0c3a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.329ex; height:3.176ex;" alt="{\displaystyle O(V^{2}E)}" loading="lazy">

</td>

<td>The push relabel algorithm maintains a preflow, i.e. a flow function with the possibility of excess in the vertices. The algorithm runs while there is a vertex with positive excess, i.e. an active vertex in the graph. The push operation increases the flow on a residual edge, and a height function on the vertices controls through which residual edges can flow be pushed. The height function is changed by the relabel operation. The proper definitions of these operations guarantee that the resulting flow function is a maximum flow.

</td></tr>

<tr>

<td><a href="Push%E2%80%93relabel_algorithm" class="mw-redirect" title="Push–relabel algorithm">Push–relabel algorithm</a> with FIFO vertex selection rule<a href="#cite_note-goldberg1988-17">[17]</a>

</td>

<td>1988

</td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(V^{3})}</annotation>

</semantics>

</math><img src="./6d79dfa438ce6a2035c8fab4878e8687ea6106c9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.554ex; height:3.176ex;" alt="{\displaystyle O(V^{3})}" loading="lazy">

</td>

<td>Push-relabel algorithm variant which always selects the most recently active vertex, and performs push operations while the excess is positive and there are admissible residual edges from this vertex.

</td></tr>

<tr>

<td><a href="Push%E2%80%93relabel_algorithm" class="mw-redirect" title="Push–relabel algorithm">Push–relabel algorithm</a> with maximum distance vertex selection rule<a href="#cite_note-cheriyan1988-18">[18]</a>

</td>

<td>1988

</td>

<msup>

</mrow>

</msup>

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(V^{2}{\sqrt {E}})}</annotation>

</semantics>

</math><img src="./3c4ed8ab52e80dc936ad64dedbb58abe07b4c49f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.265ex; height:3.176ex;" alt="{\displaystyle O(V^{2}{\sqrt {E}})}" loading="lazy">

</td>

<td>Push-relabel algorithm variant which always selects the most distant vertex from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> (i.e. the highest label vertex) but otherwise proceeds as the FIFO algorithm.

</td></tr>

<tr>

<td><a href="Push-relabel_algorithm" class="mw-redirect" title="Push-relabel algorithm">Push-relabel algorithm</a> with dynamic trees<a href="#cite_note-goldberg1988-17">[17]</a>

</td>

<td>1988

</td>

<mrow>

<mrow>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O\left(VE\log {\frac {V^{2}}{E}}\right)}</annotation>

</semantics>

</math><img src="./916e18c19095cc6c7e47eab3ebbc427f7ce743c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:16.698ex; height:6.343ex;" alt="{\displaystyle O\left(VE\log {\frac {V^{2}}{E}}\right)}" loading="lazy">

</td>

<td>The algorithm builds limited size trees on the residual graph regarding to the height function. These trees provide multilevel push operations, i.e. pushing along an entire saturating path instead of a single edge.

</td></tr>

<tr>

<td>KRT (King, Rao, Tarjan)'s algorithm<a href="#cite_note-19">[19]</a>

</td>

<td>1994

</td>

<mrow>

<mrow>

<msub>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O\left(VE\log _{\frac {E}{V\log V}}V\right)}</annotation>

</semantics>

</math><img src="./fdf218b5fbeddfa22dd7ae56c6cfd92da265e624.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:20.278ex; height:6.176ex;" alt="{\displaystyle O\left(VE\log _{\frac {E}{V\log V}}V\right)}" loading="lazy">

</td>

<td>

</td></tr>

<tr>

<td>Binary blocking flow algorithm<a href="#cite_note-20">[20]</a>

</td>

<td>1998

</td>

<mrow>

<mrow>

<msup>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O\left(E\cdot \min\{V^{2/3},E^{1/2}\}\cdot \log {\frac {V^{2}}{E}}\cdot \log U\right)}</annotation>

</semantics>

</math><img src="./888e671674fe6e57d34033199c9c238fe0dff237.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:41.043ex; height:6.343ex;" alt="{\displaystyle O\left(E\cdot \min\{V^{2/3},E^{1/2}\}\cdot \log {\frac {V^{2}}{E}}\cdot \log U\right)}" loading="lazy">

</td>

<td>

</td></tr>

<tr>

<td>James B Orlin's + KRT (King, Rao, Tarjan)'s algorithm<a href="#cite_note-orlin-9">[9]</a>

</td>

<td>2013

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(VE)}</annotation>

</semantics>

</math><img src="./60c9aa966bee3a2a9bfe780f23fd724dfb528bbd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.145ex; height:2.843ex;" alt="{\displaystyle O(VE)}" loading="lazy">

</td>

<td>Orlin's algorithm solves max-flow in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(VE)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(VE)}</annotation>

</semantics>

</math><img src="./60c9aa966bee3a2a9bfe780f23fd724dfb528bbd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.145ex; height:2.843ex;" alt="{\displaystyle O(VE)}" loading="lazy"> time for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E\leq O(V^{{\frac {16}{15}}-\epsilon })}">

<msup>

<mfrac>

</mfrac>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E\leq O(V^{{\frac {16}{15}}-\epsilon })}</annotation>

</semantics>

</math><img src="./9167cab644571ac940a655d49ea36069ee7abc27.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.723ex; height:4.009ex;" alt="{\displaystyle E\leq O(V^{{\frac {16}{15}}-\epsilon })}" loading="lazy"> while KRT solves it in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(VE)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(VE)}</annotation>

</semantics>

</math><img src="./60c9aa966bee3a2a9bfe780f23fd724dfb528bbd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.145ex; height:2.843ex;" alt="{\displaystyle O(VE)}" loading="lazy"> for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E>V^{1+\epsilon }}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E>V^{1+\epsilon }}</annotation>

</semantics>

</math><img src="./9ebfc237d73e4da6ffd2c5e516102db64fe4bdad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.791ex; height:2.676ex;" alt="{\displaystyle E>V^{1+\epsilon }}" loading="lazy">.

</td></tr>

<tr>

<td>Kathuria-Liu-Sidford algorithm<a href="#cite_note-21">[21]</a>

</td>

<td>2020

</td>

<msup>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E^{4/3+o(1)}U^{1/3}}</annotation>

</semantics>

</math><img src="./20a4bee94c87e646e6ab6f14a0334a0c9af587d7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:13.209ex; height:2.843ex;" alt="{\displaystyle E^{4/3+o(1)}U^{1/3}}" loading="lazy">

</td>

<td>Interior point methods and edge boosting using <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{p}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{p}}</annotation>

</semantics>

</math><img src="./8265d5df21cb4dab10dd3cd69a19895d649f5b45.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.029ex; height:2.843ex;" alt="{\displaystyle \ell _{p}}" loading="lazy">-norm flows. Builds on earlier algorithm of Madry, which achieved runtime <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tilde {O}}(E^{10/7}U^{1/7})}">

<mover>

</mover>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tilde {O}}(E^{10/7}U^{1/7})}</annotation>

</semantics>

</math><img src="./78eb00ca3beeb9cbc8887db8e1f95fa853483f7f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.436ex; height:3.343ex;" alt="{\displaystyle {\tilde {O}}(E^{10/7}U^{1/7})}" loading="lazy">.<a href="#cite_note-22">[22]</a>

</td></tr>

<tr>

<td>BLNPSSSW / BLLSSSW algorithm<a href="#cite_note-23">[23]</a>

</td>

<td>2020

</td>

<mover>

</mover>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tilde {O}}((E+V^{3/2})\log U)}</annotation>

</semantics>

</math><img src="./367e761e91caf0512fd1d25f8a13accb7561872e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.152ex; height:3.343ex;" alt="{\displaystyle {\tilde {O}}((E+V^{3/2})\log U)}" loading="lazy">

</td>

<td>Interior point methods and dynamic maintenance of electric flows with expander decompositions.

</td></tr>

<tr>

<td>Gao-Liu-Peng algorithm<a href="#cite_note-25">[25]</a>

</td>

<td>2021

</td>

<mover>

</mover>

</mrow>

<msup>

<mfrac>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tilde {O}}(E^{{\frac {3}{2}}-{\frac {1}{328}}}\log U)}</annotation>

</semantics>

</math><img src="./2432c56588141608e7ad7b4ae63c9ea1b17849d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.757ex; height:4.009ex;" alt="{\displaystyle {\tilde {O}}(E^{{\frac {3}{2}}-{\frac {1}{328}}}\log U)}" loading="lazy">

</td>

<td>Gao, Liu, and Peng's algorithm revolves around dynamically maintaining the augmenting electrical flows at the core of the interior point method based algorithm from [Mądry JACM ‘16]. This entails designing data structures that, in limited settings, return edges with large electric energy in a graph undergoing resistance updates.

</td></tr>

<tr>

<td>Chen, Kyng, Liu, Peng, Gutenberg and Sachdeva's algorithm<a href="#cite_note-almost_linear-10">[10]</a>

</td>

<td>2022

</td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(E^{1+o(1)}\log U)}</annotation>

</semantics>

</math><img src="./ff34c744e887ab97ab613594578cf396fefdedd1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.136ex; height:3.343ex;" alt="{\displaystyle O(E^{1+o(1)}\log U)}" loading="lazy">

The exact complexity is not stated clearly in the paper, but appears to be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E\exp O(\log ^{7/8}E\log \log E)\log U}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E\exp O(\log ^{7/8}E\log \log E)\log U}</annotation>

</semantics>

</math><img src="./195a8bae515a38598850961fcf865ce6d6bc7892.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.926ex; height:3.343ex;" alt="{\displaystyle E\exp O(\log ^{7/8}E\log \log E)\log U}" loading="lazy">

</td>

<td>Chen, Kyng, Liu, Peng, Gutenberg and Sachdeva's algorithm solves maximum flow and minimum-cost flow in almost linear time by building the flow through a sequence of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E^{1+o(1)}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E^{1+o(1)}}</annotation>

</semantics>

</math><img src="./372bbf27f5ccd83e7e2a29a61bb9b93740788c38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.025ex; height:2.843ex;" alt="{\displaystyle E^{1+o(1)}}" loading="lazy"> approximate undirected minimum-ratio cycles, each of which is computed and processed in amortized <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E^{o(1)}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E^{o(1)}}</annotation>

</semantics>

</math><img src="./56ad288fb283cfc9863a22ab9f6c14e05ee4751a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.925ex; height:2.843ex;" alt="{\displaystyle E^{o(1)}}" loading="lazy"> time using a dynamic data structure.

</td></tr>

<tr>

<td>Bernstein, Blikstad, Saranurak, Tu<a href="#cite_note-26">[26]</a>

</td>

<td>2024

</td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{2+o(1)}\log U)}</annotation>

</semantics>

</math><img src="./f5f4588eadf3e2a14f661987d86615fe16ed81e5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.737ex; height:3.343ex;" alt="{\displaystyle O(n^{2+o(1)}\log U)}" loading="lazy"> randomized algorithm when the edge capacities come from the set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{1,\dots ,U\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{1,\dots ,U\}}</annotation>

</semantics>

</math><img src="./6a8efb7525ea810518ca727aeffe25af22134524.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.448ex; height:2.843ex;" alt="{\displaystyle \{1,\dots ,U\}}" loading="lazy">

</td>

<td>The algorithm is a variant of the push-relabel algorithm by introducing the weighted variant. The paper establishes a weight function on directed and acyclic graphs (DAG), and attempts to imitate it on general graphs using directed expander hierarchies, which induce a natural vertex ordering that produces the weight function similar to that of the DAG special case. The randomization aspect (and subsequently, the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{o(1)}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{o(1)}}</annotation>

</semantics>

</math><img src="./2e9c58ecc77b8eb007fdc8af84ff291b3a5ae745.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.526ex; height:2.843ex;" alt="{\displaystyle n^{o(1)}}" loading="lazy"> factor) comes from the difficulty in applying directed expander hierarchies to the computation of sparse cuts, which do not allow for natural dynamic updating.

</td></tr></tbody></table>

For additional algorithms, see <a href="#CITEREFGoldbergTarjan1988">Goldberg & Tarjan (1988)</a>.

<div class="mw-heading mw-heading2"><h2 id="Integral_flow_theorem">Integral flow theorem</h2></div>

The integral flow theorem states that

<dl><dd>If each edge in a flow network has integral capacity, then there exists an integral maximal flow.</dd></dl>

The claim is not only that the value of the flow is an integer, which follows directly from the <a href="Max-flow_min-cut_theorem" title="Max-flow min-cut theorem">max-flow min-cut theorem</a>, but that the flow on every edge is integral. This is crucial for many <a href="Discrete_mathematics" title="Discrete mathematics">combinatorial</a> applications (see below), where the flow across an edge may encode whether the item corresponding to that edge is to be included in the set sought or not.

<div class="mw-heading mw-heading2"><h2 id="Application">Application</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Multi-source_multi-sink_maximum_flow_problem">Multi-source multi-sink maximum flow problem</h3></div>

Given a network <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=(V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N=(V,E)}</annotation>

</semantics>

</math><img src="./07d84a414272337c9fc13d80b15a4b77e01b84a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.568ex; height:2.843ex;" alt="{\displaystyle N=(V,E)}" loading="lazy"> with a set of sources <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S=\{s_{1},\ldots ,s_{n}\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S=\{s_{1},\ldots ,s_{n}\}}</annotation>

</semantics>

</math><img src="./0a903a482227b7d87cf54bc3f76e3edf55e40861.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.554ex; height:2.843ex;" alt="{\displaystyle S=\{s_{1},\ldots ,s_{n}\}}" loading="lazy"> and a set of sinks <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T=\{t_{1},\ldots ,t_{m}\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T=\{t_{1},\ldots ,t_{m}\}}</annotation>

</semantics>

</math><img src="./ab157d943429939a8fc30a5e6895db923b2ce968.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.646ex; height:2.843ex;" alt="{\displaystyle T=\{t_{1},\ldots ,t_{m}\}}" loading="lazy"> instead of only one source and one sink, we are to find the maximum flow across <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy">. We can transform the multi-source multi-sink problem into a maximum flow problem by adding a consolidated source connecting to each vertex in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> and a consolidated sink connected by each vertex in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math><img src="./ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy"> (also known as supersource and supersink) with infinite capacity on each edge (See Fig. 4.1.1.).

<div class="mw-heading mw-heading3"><h3 id="Maximum_cardinality_bipartite_matching">Maximum cardinality bipartite matching</h3></div>

Given a <a href="Bipartite_graph" title="Bipartite graph">bipartite graph</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G=(X\cup Y,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G=(X\cup Y,E)}</annotation>

</semantics>

</math><img src="./14f5ef84fc70f48d3491b91b9d503127c437ffd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.88ex; height:2.843ex;" alt="{\displaystyle G=(X\cup Y,E)}" loading="lazy">, we are to find a <a href="Maximum_cardinality_matching" title="Maximum cardinality matching">maximum cardinality matching</a> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy">, that is a matching that contains the largest possible number of edges. This problem can be transformed into a maximum flow problem by constructing a network <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=(X\cup Y\cup \{s,t\},E')}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N=(X\cup Y\cup \{s,t\},E')}</annotation>

</semantics>

</math><img src="./792f4ad8e0c2567ea3407954cf370c29a78fa453.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.691ex; height:3.009ex;" alt="{\displaystyle N=(X\cup Y\cup \{s,t\},E')}" loading="lazy">, where

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E'}</annotation>

</semantics>

</math><img src="./a574600572696493d48300245a45b8de0638ce21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle E'}" loading="lazy"> contains the edges in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> directed from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y}</annotation>

</semantics>

</math><img src="./961d67d6b454b4df2301ac571808a3538b3a6d3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.773ex; height:2.009ex;" alt="{\displaystyle Y}" loading="lazy">.</li>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (s,x)\in E'}</annotation>

</semantics>

</math><img src="./de7e2751781210ba3bae3f21ef8dd82d33a8403f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.583ex; height:3.009ex;" alt="{\displaystyle (s,x)\in E'}" loading="lazy"> for each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in X}</annotation>

</semantics>

</math><img src="./3e580967f68f36743e894aa7944f032dda6ea01d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.15ex; height:2.176ex;" alt="{\displaystyle x\in X}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (y,t)\in E'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (y,t)\in E'}</annotation>

</semantics>

</math><img src="./3cd2243bab224e1b5e4a79c57554218922a35baf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.158ex; height:3.009ex;" alt="{\displaystyle (y,t)\in E'}" loading="lazy"> for each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y\in Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y\in Y}</annotation>

</semantics>

</math><img src="./cee1c0ec36a82f33f5e3d7434d5667881b4ec323.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.769ex; height:2.509ex;" alt="{\displaystyle y\in Y}" loading="lazy">.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c(e)=1}</annotation>

</semantics>

</math><img src="./02d4aa22302096b7cae9b65c278fcb36e3365c68.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.161ex; height:2.843ex;" alt="{\displaystyle c(e)=1}" loading="lazy"> for each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e\in E'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e\in E'}</annotation>

</semantics>

</math><img src="./6153b0271c89dc2fe2a9cba36cc4d2a6b73c825a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.403ex; height:2.509ex;" alt="{\displaystyle e\in E'}" loading="lazy"> (See Fig. 4.3.1).</li></ol>

Then the value of the maximum flow in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> is equal to the size of the maximum matching in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy">, and a maximum cardinality matching can be found by taking those edges that have flow <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"> in an integral max-flow.

<div class="mw-heading mw-heading3"><h3 id="Minimum_path_cover_in_directed_acyclic_graph">Minimum path cover in directed acyclic graph</h3></div>

Given a <a href="Directed_acyclic_graph" title="Directed acyclic graph">directed acyclic graph</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G=(V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G=(V,E)}</annotation>

</semantics>

</math><img src="./644a8d85ee410b6159ca2bdb5dcb9097e2c8f182.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.331ex; height:2.843ex;" alt="{\displaystyle G=(V,E)}" loading="lazy">, we are to find the minimum number of <a href="Path_(graph_theory)" title="Path (graph theory)">vertex-disjoint paths</a> to cover each vertex in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy">. We can construct a bipartite graph <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G'=(V_{\textrm {out}}\cup V_{\textrm {in}},E')}">

<msup>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G'=(V_{\textrm {out}}\cup V_{\textrm {in}},E')}</annotation>

</semantics>

</math><img src="./7a6c3c7eca745a7260314d94c906a5f35515bbbc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.436ex; height:3.009ex;" alt="{\displaystyle G'=(V_{\textrm {out}}\cup V_{\textrm {in}},E')}" loading="lazy"> from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy">, where

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mtext> has outgoing edge(s)</mtext>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{\textrm {out}}=\{v_{\textrm {out}}\mid v\in V\land v{\text{ has outgoing edge(s)}}\}}</annotation>

</semantics>

</math><img src="./7158253806ade6d705ecf9c75ebd81cb63deb3ee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:45.67ex; height:2.843ex;" alt="{\displaystyle V_{\textrm {out}}=\{v_{\textrm {out}}\mid v\in V\land v{\text{ has outgoing edge(s)}}\}}" loading="lazy"></li>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mtext> has incoming edge(s)</mtext>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{\textrm {in}}=\{v_{\textrm {in}}\mid v\in V\land v{\text{ has incoming edge(s)}}\}}</annotation>

</semantics>

</math><img src="./897d088e645076b21c3cbb830faae6939e541d88.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:44.047ex; height:2.843ex;" alt="{\displaystyle V_{\textrm {in}}=\{v_{\textrm {in}}\mid v\in V\land v{\text{ has incoming edge(s)}}\}}" loading="lazy"></li>

<msup>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E'=\{(u_{\textrm {out}},v_{\textrm {in}})\in V_{out}\times V_{in}\mid (u,v)\in E\}}</annotation>

</semantics>

</math><img src="./5a0916ce3e8a72400b6e3e736a166315c918d207.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:42.009ex; height:3.009ex;" alt="{\displaystyle E'=\{(u_{\textrm {out}},v_{\textrm {in}})\in V_{out}\times V_{in}\mid (u,v)\in E\}}" loading="lazy">.</li></ol>

Then it can be shown that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G'}</annotation>

</semantics>

</math><img src="./76634fad5818a777669a77cd8c86d1d816e4c402.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.511ex; height:2.509ex;" alt="{\displaystyle G'}" loading="lazy"> has a matching <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> of size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> if and only if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> has a vertex-disjoint path cover <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> containing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> edges and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-m}</annotation>

</semantics>

</math><img src="./3a9677b812ea9ee4d4538767f9aef960c69aca59.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.276ex; height:2.176ex;" alt="{\displaystyle n-m}" loading="lazy"> paths, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> is the number of vertices in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy">. Therefore, the problem can be solved by finding the maximum cardinality matching in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G'}</annotation>

</semantics>

</math><img src="./76634fad5818a777669a77cd8c86d1d816e4c402.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.511ex; height:2.509ex;" alt="{\displaystyle G'}" loading="lazy"> instead.

Assume we have found a matching <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G'}</annotation>

</semantics>

</math><img src="./76634fad5818a777669a77cd8c86d1d816e4c402.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.511ex; height:2.509ex;" alt="{\displaystyle G'}" loading="lazy">, and constructed the cover <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> from it. Intuitively, if two vertices <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u_{\mathrm {out} },v_{\mathrm {in} }}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u_{\mathrm {out} },v_{\mathrm {in} }}</annotation>

</semantics>

</math><img src="./050da7c569c836f1975fc87e8db5417441d2a231.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.703ex; height:2.009ex;" alt="{\displaystyle u_{\mathrm {out} },v_{\mathrm {in} }}" loading="lazy"> are matched in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy">, then the edge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (u,v)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (u,v)}</annotation>

</semantics>

</math><img src="./eadf12294edccd7a29c99cfc1765e4a14bf47e58.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.301ex; height:2.843ex;" alt="{\displaystyle (u,v)}" loading="lazy"> is contained in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy">. Clearly the number of edges in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy">. To see that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> is vertex-disjoint, consider the following:

<ol><li>Each vertex <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{\textrm {out}}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{\textrm {out}}}</annotation>

</semantics>

</math><img src="./f85426095ee088bbc344b3c84bd73236ae0fdb2e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.735ex; height:2.009ex;" alt="{\displaystyle v_{\textrm {out}}}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G'}</annotation>

</semantics>

</math><img src="./76634fad5818a777669a77cd8c86d1d816e4c402.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.511ex; height:2.509ex;" alt="{\displaystyle G'}" loading="lazy"> can either be non-matched in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy">, in which case there are no edges leaving <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy">; or it can be matched, in which case there is exactly one edge leaving <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy">. In either case, no more than one edge leaves any vertex <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy">.</li>

<li>Similarly for each vertex <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{\textrm {in}}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{\textrm {in}}}</annotation>

</semantics>

</math><img src="./6a4f7252ce5ef538210915c2c0cae771dbbe07c6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.731ex; height:2.009ex;" alt="{\displaystyle v_{\textrm {in}}}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G'}</annotation>

</semantics>

</math><img src="./76634fad5818a777669a77cd8c86d1d816e4c402.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.511ex; height:2.509ex;" alt="{\displaystyle G'}" loading="lazy"> – if it is matched, there is a single incoming edge into <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy">; otherwise <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> has no incoming edges in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy">.</li></ol>

Thus no vertex has two incoming or two outgoing edges in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy">, which means all paths in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> are vertex-disjoint.

To show that the cover <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> has size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-m}</annotation>

</semantics>

</math><img src="./3a9677b812ea9ee4d4538767f9aef960c69aca59.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.276ex; height:2.176ex;" alt="{\displaystyle n-m}" loading="lazy">, we start with an empty cover and build it incrementally. To add a vertex <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u}</annotation>

</semantics>

</math><img src="./c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" loading="lazy"> to the cover, we can either add it to an existing path, or create a new path of length zero starting at that vertex. The former case is applicable whenever either <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (u,v)\in E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (u,v)\in E}</annotation>

</semantics>

</math><img src="./fb3670c33f5481059c095a58c9ebbd60dc6f35f8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.917ex; height:2.843ex;" alt="{\displaystyle (u,v)\in E}" loading="lazy"> and some path in the cover starts at <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy">, or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (v,u)\in E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (v,u)\in E}</annotation>

</semantics>

</math><img src="./b3613740e5435a23ccafec670ec7da8618f0a542.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.917ex; height:2.843ex;" alt="{\displaystyle (v,u)\in E}" loading="lazy"> and some path ends at <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy">. The latter case is always applicable. In the former case, the total number of edges in the cover is increased by 1 and the number of paths stays the same; in the latter case the number of paths is increased and the number of edges stays the same. It is now clear that after covering all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> vertices, the sum of the number of paths and edges in the cover is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">. Therefore, if the number of edges in the cover is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy">, the number of paths is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-m}</annotation>

</semantics>

</math><img src="./3a9677b812ea9ee4d4538767f9aef960c69aca59.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.276ex; height:2.176ex;" alt="{\displaystyle n-m}" loading="lazy">.

<div class="mw-heading mw-heading3"><h3 id="Maximum_flow_with_vertex_capacities">Maximum flow with vertex capacities</h3></div>

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=(V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N=(V,E)}</annotation>

</semantics>

</math><img src="./07d84a414272337c9fc13d80b15a4b77e01b84a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.568ex; height:2.843ex;" alt="{\displaystyle N=(V,E)}" loading="lazy"> be a network. Suppose there is capacity at each node in addition to edge capacity, that is, a mapping <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c:V\to \mathbb {R} ^{+},}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c:V\to \mathbb {R} ^{+},}</annotation>

</semantics>

</math><img src="./c58a36cab32df819909274df92a0e0cb97ae1439.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.181ex; height:2.843ex;" alt="{\displaystyle c:V\to \mathbb {R} ^{+},}" loading="lazy"> such that the flow <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> has to satisfy not only the capacity constraint and the conservation of flows, but also the vertex capacity constraint

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i\in V}f_{iv}\leq c(v)\qquad \forall v\in V\backslash \{s,t\}.}</annotation>

</semantics>

</math><img src="./3b4843d461562523d45f717c6d40a4ee8b287660.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:32.312ex; height:5.676ex;" alt="{\displaystyle \sum _{i\in V}f_{iv}\leq c(v)\qquad \forall v\in V\backslash \{s,t\}.}" loading="lazy"></dd></dl>

In other words, the amount of flow passing through a vertex cannot exceed its capacity. To find the maximum flow across <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy">, we can transform the problem into the maximum flow problem in the original sense by expanding <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy">. First, each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v\in V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v\in V}</annotation>

</semantics>

</math><img src="./99886ebbde63daa0224fb9bf56fa11b3c8a6f4fb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.756ex; height:2.176ex;" alt="{\displaystyle v\in V}" loading="lazy"> is replaced by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{\text{in}}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{\text{in}}}</annotation>

</semantics>

</math><img src="./1c2620c10ee74466ddb70d1d1693fc81da3b5f52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.731ex; height:2.009ex;" alt="{\displaystyle v_{\text{in}}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{\text{out}}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{\text{out}}}</annotation>

</semantics>

</math><img src="./6995972aaa3768ed8eccb42e15f0347fcad98d76.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.735ex; height:2.009ex;" alt="{\displaystyle v_{\text{out}}}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{\text{in}}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{\text{in}}}</annotation>

</semantics>

</math><img src="./1c2620c10ee74466ddb70d1d1693fc81da3b5f52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.731ex; height:2.009ex;" alt="{\displaystyle v_{\text{in}}}" loading="lazy"> is connected by edges going into <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{\text{out}}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{\text{out}}}</annotation>

</semantics>

</math><img src="./6995972aaa3768ed8eccb42e15f0347fcad98d76.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.735ex; height:2.009ex;" alt="{\displaystyle v_{\text{out}}}" loading="lazy"> is connected to edges coming out from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy">, then assign capacity <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c(v)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c(v)}</annotation>

</semantics>

</math><img src="./5a7ed821a9151fd3f6bf83b190e2941d264e05a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.944ex; height:2.843ex;" alt="{\displaystyle c(v)}" loading="lazy"> to the edge connecting <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{\text{in}}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{\text{in}}}</annotation>

</semantics>

</math><img src="./1c2620c10ee74466ddb70d1d1693fc81da3b5f52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.731ex; height:2.009ex;" alt="{\displaystyle v_{\text{in}}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{\text{out}}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{\text{out}}}</annotation>

</semantics>

</math><img src="./6995972aaa3768ed8eccb42e15f0347fcad98d76.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.735ex; height:2.009ex;" alt="{\displaystyle v_{\text{out}}}" loading="lazy"> (see Fig. 4.4.1). In this expanded network, the vertex capacity constraint is removed and therefore the problem can be treated as the original maximum flow problem.

<div class="mw-heading mw-heading3"><h3 id="Maximum_number_of_paths_from_s_to_t">Maximum number of paths from s to t</h3></div>

Given a directed graph <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G=(V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G=(V,E)}</annotation>

</semantics>

</math><img src="./644a8d85ee410b6159ca2bdb5dcb9097e2c8f182.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.331ex; height:2.843ex;" alt="{\displaystyle G=(V,E)}" loading="lazy"> and two vertices <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy">, we are to find the maximum number of paths from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy">. This problem has several variants:

1. The paths must be edge-disjoint. This problem can be transformed to a maximum flow problem by constructing a network <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=(V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N=(V,E)}</annotation>

</semantics>

</math><img src="./07d84a414272337c9fc13d80b15a4b77e01b84a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.568ex; height:2.843ex;" alt="{\displaystyle N=(V,E)}" loading="lazy"> from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy">, with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> being the source and the sink of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> respectively, and assigning each edge a capacity of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy">. In this network, the maximum flow is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> iff there are <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> edge-disjoint paths.

2. The paths must be independent, i.e., vertex-disjoint (except for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy">). We can construct a network <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=(V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N=(V,E)}</annotation>

</semantics>

</math><img src="./07d84a414272337c9fc13d80b15a4b77e01b84a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.568ex; height:2.843ex;" alt="{\displaystyle N=(V,E)}" loading="lazy"> from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> with vertex capacities, where the capacities of all vertices and all edges are <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy">. Then the value of the maximum flow is equal to the maximum number of independent paths from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy">.

3. In addition to the paths being edge-disjoint and/or vertex disjoint, the paths also have a length constraint: we count only paths whose length is exactly <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">, or at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">. Most variants of this problem are NP-complete, except for small values of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">.<a href="#cite_note-27">[27]</a>

<div class="mw-heading mw-heading3"><h3 id="Closure_problem">Closure problem</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Closure_problem" title="Closure problem">Closure problem</a></div>

A closure of a directed graph is a set of vertices C, such that no edges leave C. The closure problem is the task of finding the maximum-weight or minimum-weight closure in a vertex-weighted directed graph. It may be solved in <a href="Time_complexity" title="Time complexity">polynomial time</a> using a reduction to the maximum flow problem.

<div class="mw-heading mw-heading2"><h2 id="Real_world_applications">Real world applications</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Baseball_elimination">Baseball elimination</h3></div>

In the <a href="Baseball" title="Baseball">baseball</a> elimination problem there are n teams competing in a league. At a specific stage of the league season, wi is the number of wins and ri is the number of games left to play for team i and rij is the number of games left against team j. A team is eliminated if it has no chance to finish the season in the first place. The task of the baseball elimination problem is to determine which teams are eliminated at each point during the season. Schwartz<a href="#cite_note-28">[28]</a> proposed a method which reduces this problem to maximum network flow. In this method a network is created to determine whether team k is eliminated.

Let G = (V, E) be a network with s,t ∈ V being the source and the sink respectively. One adds a game nodeij – which represents the number of plays between these two teams. We also add a team node for each team and connect each game node {i, j} with i < j to V, and connects each of them from s by an edge with capacity rij – which represents the number of plays between these two teams. We also add a team node for each team and connect each game node {i, j} with two team nodes i and j to ensure one of them wins. One does not need to restrict the flow value on these edges. Finally, edges are made from team node i to the sink node t and the capacity of wk + rk – wi is set to prevent team i from winning more than wk + rk.

Let S be the set of all teams participating in the league and let

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r(S-\{k\})=\sum _{i,j\in \{S-\{k\}\} \atop i<j}r_{ij}}</annotation>

</semantics>

</math><img src="./74b9cd699a360d7f1e756efcc6c45512a6f55011.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.838ex; width:24.838ex; height:7.343ex;" alt="{\displaystyle r(S-\{k\})=\sum _{i,j\in \{S-\{k\}\} \atop i<j}r_{ij}}" loading="lazy">.</dd></dl>

In this method it is claimed team k is not eliminated if and only if a flow value of size r(S − {k}) exists in network G. In the mentioned article it is proved that this flow value is the maximum flow value from s to t.

<div class="mw-heading mw-heading3"><h3 id="Airline_scheduling">Airline scheduling</h3></div>

In the airline industry a major problem is the scheduling of the flight crews. The airline scheduling problem can be considered as an application of extended maximum network flow. The input of this problem is a set of flights F which contains the information about where and when each flight departs and arrives. In one version of airline scheduling the goal is to produce a feasible schedule with at most k crews.

To solve this problem one uses a variation of the <a href="Circulation_problem" title="Circulation problem">circulation problem</a> called bounded circulation which is the generalization of <a href="Flow_network" title="Flow network">network flow</a> problems, with the added constraint of a lower bound on edge flows.

Let G = (V, E) be a network with s,t ∈ V as the source and the sink nodes. For the source and destination of every flight i, one adds two nodes to V, node si as the source and node di as the destination node of flight i. One also adds the following edges to E:

<ol><li>An edge with capacity [0, 1] between s and each si.</li>

<li>An edge with capacity [0, 1] between each di and t.</li>

<li>An edge with capacity [1, 1] between each pair of si and di.</li>

<li>An edge with capacity [0, 1] between each di and sj, if source sj is reachable with a reasonable amount of time and cost from the destination of flight i.</li>

<li>An edge with capacity [0, <a href="%E2%88%9E" class="mw-redirect" title="∞">∞</a>] between s and t.</li></ol>

In the mentioned method, it is claimed and proved that finding a flow value of k in G between s and t is equal to finding a feasible schedule for flight set F with at most k crews.<a href="#cite_note-ITA-29">[29]</a>

Another version of airline scheduling is finding the minimum needed crews to perform all the flights. To find an answer to this problem, a bipartite graph <var style="padding-right: 1px;">G'</var> = (A ∪ B, E) is created where each flight has a copy in set A and set B. If the same plane can perform flight j after flight i, i∈A is connected to j∈B. A matching in G' induces a schedule for F and obviously maximum bipartite matching in this graph produces an airline schedule with minimum number of crews.<a href="#cite_note-ITA-29">[29]</a> As it is mentioned in the Application part of this article, the maximum cardinality bipartite matching is an application of maximum flow problem.

<div class="mw-heading mw-heading3"><h3 id="Circulation–demand_problem">Circulation–demand problem</h3></div>

There are some factories that produce goods and some villages where the goods have to be delivered. They are connected by a networks of roads with each road having a capacity c for maximum goods that can flow through it. The problem is to find if there is a circulation that satisfies the demand.

This problem can be transformed into a maximum-flow problem.

<ol><li>Add a source node s and add edges from it to every factory node fi with capacity pi where pi is the production rate of factory fi.</li>

<li>Add a sink node t and add edges from all villages vi to t with capacity di where di is the demand rate of village vi.</li></ol>

Let G = (V, E) be this new network. There exists a circulation that satisfies the demand if and only if :

<dl><dd>Maximum flow value(G) <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle =\sum _{i\in v}d_{i}}">

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle =\sum _{i\in v}d_{i}}</annotation>

</semantics>

</math><img src="./1f3efff115bf5c5aa34965d1f232869c82050c36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:8.204ex; height:5.509ex;" alt="{\displaystyle =\sum _{i\in v}d_{i}}" loading="lazy">.</dd></dl>

If there exists a circulation, looking at the max-flow solution would give the answer as to how much goods have to be sent on a particular road for satisfying the demands.

The problem can be extended by adding a lower bound on the flow on some edges.<a href="#cite_note-30">[30]</a>

<div class="mw-heading mw-heading3"><h3 id="Image_segmentation">Image segmentation</h3></div>

In their book, Kleinberg and Tardos present an algorithm for <a href="Image_segmentation" title="Image segmentation">segmenting</a> an image.<a href="#cite_note-32">[32]</a> They present an algorithm to find the background and the foreground in an image. More precisely, the algorithm takes a bitmap as an input modelled as follows: ai ≥ 0 is the likelihood that pixel i belongs to the foreground, bi ≥ 0 in the likelihood that pixel i belongs to the background, and pij is the penalty if two adjacent pixels i and j are placed one in the foreground and the other in the background. The goal is to find a partition (A, B) of the set of pixels that maximize the following quantity

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<mtr>

<mtd>

<mtext> adjacent</mtext>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q(A,B)=\sum _{i\in A}a_{i}+\sum _{i\in B}b_{i}-\sum _{\begin{matrix}i,j{\text{ adjacent}}\\|A\cap \{i,j\}|=1\end{matrix}}p_{ij}}</annotation>

</semantics>

</math><img src="./0d973c6390daeb988530cc6653090a8ae381737f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.171ex; width:39.985ex; height:8.676ex;" alt="{\displaystyle q(A,B)=\sum _{i\in A}a_{i}+\sum _{i\in B}b_{i}-\sum _{\begin{matrix}i,j{\text{ adjacent}}\\|A\cap \{i,j\}|=1\end{matrix}}p_{ij}}" loading="lazy">,</dd></dl>

Indeed, for pixels in A (considered as the foreground), we gain ai; for all pixels in B (considered as the background), we gain bi. On the border, between two adjacent pixels i and j, we loose pij. It is equivalent to minimize the quantity

<msup>

</msup>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<mtr>

<mtd>

<mtext> adjacent</mtext>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q'(A,B)=\sum _{i\in A}b_{i}+\sum _{i\in B}a_{i}+\sum _{\begin{matrix}i,j{\text{ adjacent}}\\|A\cap \{i,j\}|=1\end{matrix}}p_{ij}}</annotation>

</semantics>

</math><img src="./242ee5a41091d141051f77da910263c53217c277.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.171ex; width:40.68ex; height:8.676ex;" alt="{\displaystyle q'(A,B)=\sum _{i\in A}b_{i}+\sum _{i\in B}a_{i}+\sum _{\begin{matrix}i,j{\text{ adjacent}}\\|A\cap \{i,j\}|=1\end{matrix}}p_{ij}}" loading="lazy"></dd></dl>

because

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q(A,B)=\sum _{i\in A\cup B}a_{i}+\sum _{i\in A\cup B}b_{i}-q'(A,B).}</annotation>

</semantics>

</math><img src="./e89159cb7c8d4adf3791920fca664c21727f7960.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:40.041ex; height:5.676ex;" alt="{\displaystyle q(A,B)=\sum _{i\in A\cup B}a_{i}+\sum _{i\in A\cup B}b_{i}-q'(A,B).}" loading="lazy"></dd></dl>

We now construct the network whose nodes are the pixel, plus a source and a sink, see Figure on the right. We connect the source to pixel i by an edge of weight ai. We connect the pixel i to the sink by an edge of weight bi. We connect pixel i to pixel j with weight pij. Now, it remains to compute a minimum cut in that network (or equivalently a maximum flow). The last figure shows a minimum cut.

<div class="mw-heading mw-heading2"><h2 id="Extensions">Extensions</h2></div>

1. In the <a href="Minimum-cost_flow_problem" title="Minimum-cost flow problem">minimum-cost flow problem</a>, each edge (u,v) also has a cost-coefficient auv in addition to its capacity. If the flow through the edge is fuv, then the total cost is auvfuv. It is required to find a flow of a given size d, with the smallest cost. In most variants, the cost-coefficients may be either positive or negative. There are various polynomial-time algorithms for this problem.

2. The maximum-flow problem can be augmented by disjunctive constraints: a negative disjunctive constraint says that a certain pair of edges cannot simultaneously have a nonzero flow; a positive disjunctive constraints says that, in a certain pair of edges, at least one must have a nonzero flow. With negative constraints, the problem becomes <a href="Strongly_NP-hard" class="mw-redirect" title="Strongly NP-hard">strongly NP-hard</a> even for simple networks. With positive constraints, the problem is polynomial if fractional flows are allowed, but may be <a href="Strongly_NP-hard" class="mw-redirect" title="Strongly NP-hard">strongly NP-hard</a> when the flows must be integral.<a href="#cite_note-33">[33]</a>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFSchrijver2002" class="citation journal cs1">Schrijver, A. (2002). "On the history of the transportation and maximum flow problems". Mathematical Programming. 91 (3): 437–445. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.5134">10.1.1.23.5134</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs101070100259">10.1007/s101070100259</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:10210675">10210675</a>.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFGassAssad2005" class="citation book cs1">Gass, Saul I.; Assad, Arjang A. (2005). "Mathematical, algorithmic and professional developments of operations research from 1951 to 1956". An Annotated Timeline of Operations Research. International Series in Operations Research & Management Science. Vol. 75. pp. 79–110. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F0-387-25837-X_5">10.1007/0-387-25837-X_5</a> (inactive 1 July 2025). <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4020-8116-3</bdi>.</cite><code class="cs1-code">{{cite book}}</code>: CS1 maint: DOI inactive as of July 2025 (link)

</li>

<li id="cite_note-:2-3">^ <a href="#cite_ref-:2_3-0">a</a> <a href="#cite_ref-:2_3-1">b</a> <cite id="CITEREFHarrisRoss1955" class="citation journal cs1"><a href="Ted_Harris_(mathematician)" title="Ted Harris (mathematician)">Harris, T. E.</a>; Ross, F. S. (1955). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20140108021700/http://www.dtic.mil/dtic/tr/fulltext/u2/093458.pdf">"Fundamentals of a Method for Evaluating Rail Net Capacities"</a> (PDF). Research Memorandum. Archived from <a rel="nofollow" class="external text" href="http://www.dtic.mil/dtic/tr/fulltext/u2/093458.pdf">the original</a> (PDF) on 8 January 2014.</cite>

</li>

<li id="cite_note-:1-4">^ <a href="#cite_ref-:1_4-0">a</a> <a href="#cite_ref-:1_4-1">b</a> <cite id="CITEREFFordFulkerson1956" class="citation journal cs1"><a href="L._R._Ford%2C_Jr." class="mw-redirect" title="L. R. Ford, Jr.">Ford, L. R.</a>; <a href="D._R._Fulkerson" title="D. R. Fulkerson">Fulkerson, D. R.</a> (1956). <a rel="nofollow" class="external text" href="https://doi.org/10.4153%2FCJM-1956-045-5">"Maximal flow through a network"</a>. <a href="Canadian_Journal_of_Mathematics" title="Canadian Journal of Mathematics">Canadian Journal of Mathematics</a>. 8: 399–404. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.4153%2FCJM-1956-045-5">10.4153/CJM-1956-045-5</a>.</cite>

</li>

<li id="cite_note-:3-5">^ <a href="#cite_ref-:3_5-0">a</a> <a href="#cite_ref-:3_5-1">b</a> Ford, L.R., Jr.; Fulkerson, D.R., Flows in Networks, Princeton University Press (1962).

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFSherman2013" class="citation book cs1">Sherman, Jonah (2013). "Nearly Maximum Flows in Nearly Linear Time". Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science. pp. 263–269. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1304.2077">1304.2077</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FFOCS.2013.36">10.1109/FOCS.2013.36</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-7695-5135-7</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:14681906">14681906</a>.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFKelnerLeeOrecchiaSidford2014" class="citation book cs1">Kelner, J. A.; Lee, Y. T.; Orecchia, L.; Sidford, A. (2014). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20160303170302/http://math.mit.edu/~kelner/Publications/Docs/klos_maxflow_main.pdf">"An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations"</a> (PDF). Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. p. 217. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1304.2338">1304.2338</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F1.9781611973402.16">10.1137/1.9781611973402.16</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-61197-338-9</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:10733914">10733914</a>. Archived from <a rel="nofollow" class="external text" href="http://math.mit.edu/~kelner/Publications/Docs/klos_maxflow_main.pdf">the original</a> (PDF) on 3 March 2016.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFKnight2014" class="citation web cs1">Knight, Helen (7 January 2014). <a rel="nofollow" class="external text" href="http://web.mit.edu/newsoffice/2013/new-algorithm-can-dramatically-streamline-solutions-to-the-max-flow-problem-0107.html">"New algorithm can dramatically streamline solutions to the 'max flow' problem"</a>. MIT News. Retrieved 8 January 2014.</cite>

</li>

<li id="cite_note-orlin-9">^ <a href="#cite_ref-orlin_9-0">a</a> <a href="#cite_ref-orlin_9-1">b</a> <cite id="CITEREFOrlin2013" class="citation book cs1">Orlin, James B. (2013). "Max flows in O(nm) time, or better". Proceedings of the forty-fifth annual ACM symposium on Theory of Computing. pp. 765–774. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.259.5759">10.1.1.259.5759</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2488608.2488705">10.1145/2488608.2488705</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781450320290</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:207205207">207205207</a>.</cite>

</li>

<li id="cite_note-almost_linear-10">^ <a href="#cite_ref-almost_linear_10-0">a</a> <a href="#cite_ref-almost_linear_10-1">b</a> <cite id="CITEREFChenKyngLiuGutenberg2022" class="citation arxiv cs1">Chen, L.; Kyng, R.; Liu, Y.P.; Gutenberg, M.P.; Sachdeva, S. (2022). "Maximum Flow and Minimum-Cost Flow in Almost-Linear Time". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2203.00671">2203.00671</a> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.DS">cs.DS</a>].</cite>

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFKlarreich2022" class="citation web cs1">Klarreich, Erica (8 June 2022). <a rel="nofollow" class="external text" href="https://www.quantamagazine.org/researchers-achieve-absurdly-fast-algorithm-for-network-flow-20220608/">"Researchers Achieve 'Absurdly Fast' Algorithm for Network Flow"</a>. Quanta Magazine. Retrieved 8 June 2022.</cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFBernsteinNanongkaiWulff-Nilsen2022" class="citation arxiv cs1">Bernstein, Aaron; Nanongkai, Danupon; Wulff-Nilsen, Christian (30 October 2022). "Negative-Weight Single-Source Shortest Paths in Near-linear Time". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2203.03456">2203.03456</a> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.DS">cs.DS</a>].</cite>

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <cite id="CITEREFBrubaker2023" class="citation web cs1">Brubaker, Ben (18 January 2023). <a rel="nofollow" class="external text" href="https://www.quantamagazine.org/finally-a-fast-algorithm-for-shortest-paths-on-negative-graphs-20230118/">"Finally, a Fast Algorithm for Shortest Paths on Negative Graphs"</a>. Quanta Magazine. Retrieved 25 January 2023.</cite>

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://focs2022.eecs.berkeley.edu/awards.html">"FOCS 2022"</a>. focs2022.eecs.berkeley.edu. Retrieved 25 January 2023.</cite>

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> <cite id="CITEREFSantosh" class="citation web cs1">Santosh, Nagarakatte. <a rel="nofollow" class="external text" href="https://www.cs.rutgers.edu/news-events/news/news-item/focs-2022-best-paper-award-for-prof-aaron-bernstein-s-paper">"FOCS 2022 Best Paper Award for Prof. Aaron Bernstein's Paper"</a>. www.cs.rutgers.edu. Retrieved 25 January 2023.</cite>

</li>

<li id="cite_note-16"><a href="#cite_ref-16">^</a> <cite id="CITEREFMalhotraKumarMaheshwari1978" class="citation journal cs1">Malhotra, V.M.; Kumar, M. Pramodh; Maheshwari, S.N. (1978). <a rel="nofollow" class="external text" href="https://eprints.utas.edu.au/160/1/iplFlow.pdf">"An <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|V|^{3})}">

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|V|^{3})}</annotation>

</semantics>

</math><img src="./04ad8b53a2cea864c6d746895cc7397971f72912.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.718ex; height:3.343ex;" alt="{\displaystyle O(|V|^{3})}" loading="lazy"> algorithm for finding maximum flows in networks"</a> (PDF). Information Processing Letters. 7 (6): 277–278. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0020-0190%2878%2990016-9">10.1016/0020-0190(78)90016-9</a>.</cite>

</li>

<li id="cite_note-goldberg1988-17">^ <a href="#cite_ref-goldberg1988_17-0">a</a> <a href="#cite_ref-goldberg1988_17-1">b</a> <a href="#cite_ref-goldberg1988_17-2">c</a> <cite id="CITEREFGoldbergTarjan1988" class="citation journal cs1"><a href="Andrew_V._Goldberg" title="Andrew V. Goldberg">Goldberg, A. V.</a>; <a href="Robert_E._Tarjan" class="mw-redirect" title="Robert E. Tarjan">Tarjan, R. E.</a> (1988). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F48014.61051">"A new approach to the maximum-flow problem"</a>. <a href="Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a>. 35 (4): 921. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F48014.61051">10.1145/48014.61051</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:52152408">52152408</a>.</cite>

</li>

<li id="cite_note-cheriyan1988-18"><a href="#cite_ref-cheriyan1988_18-0">^</a> <cite id="CITEREFCheriyanMaheshwari1988" class="citation book cs1">Cheriyan, J.; Maheshwari, S. N. (1988). "Analysis of preflow push algorithms for maximum network flow". Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science. Vol. 338. pp. 30–48. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-50517-2_69">10.1007/3-540-50517-2_69</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-50517-4</bdi>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0302-9743">0302-9743</a>.</cite>

</li>

<li id="cite_note-19"><a href="#cite_ref-19">^</a> <cite id="CITEREFKingRaoTarjan1994" class="citation journal cs1">King, V.; Rao, S.; Tarjan, R. (1994). "A Faster Deterministic Maximum Flow Algorithm". Journal of Algorithms. 17 (3): 447–474. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjagm.1994.1044">10.1006/jagm.1994.1044</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:15493">15493</a>.</cite>

</li>

<li id="cite_note-20"><a href="#cite_ref-20">^</a> <cite id="CITEREFGoldbergRao1998" class="citation journal cs1"><a href="Andrew_V._Goldberg" title="Andrew V. Goldberg">Goldberg, A. V.</a>; Rao, S. (1998). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F290179.290181">"Beyond the flow decomposition barrier"</a>. <a href="Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a>. 45 (5): 783. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F290179.290181">10.1145/290179.290181</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:96030">96030</a>.</cite>

</li>

<li id="cite_note-21"><a href="#cite_ref-21">^</a> <cite id="CITEREFKathuriaLiuSidford2020" class="citation book cs1">Kathuria, T.; Liu, Y.P.; Sidford, A. (16–19 November 2020). Unit Capacity Maxflow in Almost <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(m^{4/3})}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(m^{4/3})}</annotation>

</semantics>

</math><img src="./015ba5d8bc8768f379c11a579559725f4a968280.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.321ex; height:3.343ex;" alt="{\displaystyle O(m^{4/3})}" loading="lazy"> Time. Durham, NC, USA: IEEE. pp. 119–130.</cite>

</li>

<li id="cite_note-22"><a href="#cite_ref-22">^</a> <cite id="CITEREFMadry2016" class="citation book cs1">Madry, Aleksander (9–11 October 2016). Computing Maximum Flow with Augmenting Electrical Flows. New Brunswick, New Jersey: IEEE. pp. 593–602.</cite>

</li>

<li id="cite_note-23"><a href="#cite_ref-23">^</a> <cite id="CITEREFBrandLeeNanongkaiPeng2020" class="citation book cs1">Brand, J. vd; Lee, Y.T.; Nanongkai, D.; Peng, R.; Saranurak, T.; Sidford, A.; Song, Z.; Wang, D. (16–19 November 2020). Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs. Durham, NC, USA: IEEE. pp. 919–930.</cite>

</li>

<li id="cite_note-24"><a href="#cite_ref-24">^</a> <cite id="CITEREFBrandLeeLiuSaranurak2021" class="citation arxiv cs1">Brand, J. vd; Lee, Y.T.; Liu, Y.P.; Saranurak, T.; Sidford, A; Song, Z.; Wang, D. (2021). "Minimum Cost Flows, MDPs, and ℓ1-Regression in Nearly Linear Time for Dense Instances". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2101.05719">2101.05719</a> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.DS">cs.DS</a>].</cite>

</li>

<li id="cite_note-25"><a href="#cite_ref-25">^</a> <cite id="CITEREFGaoLiuPeng2021" class="citation arxiv cs1">Gao, Y.; Liu, Y.P.; Peng, R. (2021). "Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2101.07233">2101.07233</a> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.DS">cs.DS</a>].</cite>

</li>

<li id="cite_note-26"><a href="#cite_ref-26">^</a> <cite id="CITEREFBernsteinBlikstadSaranurakTu2024" class="citation arxiv cs1">Bernstein, A.; Blikstad, J.; Saranurak, T.; Tu, T. (2024). "Maximum Flow by Augmenting Paths in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{2+o(1)}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{2+o(1)}}</annotation>

</semantics>

</math><img src="./878f894ddcb848657f3716dfd5734da3a2fc6e2c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.626ex; height:2.843ex;" alt="{\displaystyle n^{2+o(1)}}" loading="lazy"> Time". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2406.03648">2406.03648</a> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.DS">cs.DS</a>].</cite>

</li>

<li id="cite_note-27"><a href="#cite_ref-27">^</a> <cite id="CITEREFItaiPerlShiloach1982" class="citation journal cs1">Itai, A.; Perl, Y.; Shiloach, Y. (1982). "The complexity of finding maximum disjoint paths with length constraints". Networks. 12 (3): 277–286. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2Fnet.3230120306">10.1002/net.3230120306</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1097-0037">1097-0037</a>.</cite>

</li>

<li id="cite_note-28"><a href="#cite_ref-28">^</a> <cite id="CITEREFSchwartz1966" class="citation journal cs1">Schwartz, B. L. (1966). "Possible Winners in Partially Completed Tournaments". <a href="SIAM_Review" class="mw-redirect" title="SIAM Review">SIAM Review</a>. 8 (3): 302–308. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1966SIAMR...8..302S">1966SIAMR...8..302S</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F1008062">10.1137/1008062</a>. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2028206">2028206</a>.</cite>

</li>

<li id="cite_note-ITA-29">^ <a href="#cite_ref-ITA_29-0">a</a> <a href="#cite_ref-ITA_29-1">b</a> <cite id="CITEREFThomas_H._Cormen,_Charles_E._Leiserson,_Ronald_L._Rivest,_and_Clifford_Stein2001" class="citation book cs1"><a href="Thomas_H._Cormen" title="Thomas H. Cormen">Thomas H. Cormen</a>, <a href="Charles_E._Leiserson" title="Charles E. Leiserson">Charles E. Leiserson</a>, <a href="Ronald_L._Rivest" class="mw-redirect" title="Ronald L. Rivest">Ronald L. Rivest</a>, and <a href="Clifford_Stein" title="Clifford Stein">Clifford Stein</a> (2001). "26. Maximum Flow". <a href="Introduction_to_Algorithms" title="Introduction to Algorithms">Introduction to Algorithms, Second Edition</a>. MIT Press and McGraw-Hill. pp. 643–668. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-262-03293-3</bdi>.</cite><code class="cs1-code">{{cite book}}</code>: CS1 maint: multiple names: authors list (link)

</li>

<li id="cite_note-30"><a href="#cite_ref-30">^</a> <cite id="CITEREFCarl_Kingsford" class="citation web cs1">Carl Kingsford. <a rel="nofollow" class="external text" href="https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/flowext.pdf">"Max-flow extensions: circulations with demands"</a> (PDF).</cite>

</li>

<li id="cite_note-31"><a href="#cite_ref-31">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20191222173132/https://gitlab.com/francois.schwarzentruber/imagesegmentationwithmaxflow">"Project imagesegmentationwithmaxflow, that contains the source code to produce these illustrations"</a>. GitLab. Archived from <a rel="nofollow" class="external text" href="https://gitlab.com/francois.schwarzentruber/imagesegmentationwithmaxflow">the original</a> on 22 December 2019. Retrieved 22 December 2019.</cite>

</li>

<li id="cite_note-32"><a href="#cite_ref-32">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.pearson.com/us/higher-education/program/Kleinberg-Algorithm-Design/PGM319216.html">"Algorithm Design"</a>. pearson.com. Retrieved 21 December 2019.</cite>

</li>

<li id="cite_note-33"><a href="#cite_ref-33">^</a> <cite id="CITEREFSchauerPferschy2013" class="citation journal cs1">Schauer, Joachim; Pferschy, Ulrich (1 July 2013). "The maximum flow problem with disjunctive constraints". Journal of Combinatorial Optimization. 26 (1): 109–119. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.414.4496">10.1.1.414.4496</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs10878-011-9438-7">10.1007/s10878-011-9438-7</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1382-6905">1382-6905</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:6598669">6598669</a>.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFJoseph_Cheriyan_and_Kurt_Mehlhorn1999" class="citation journal cs1">Joseph Cheriyan and <a href="Kurt_Mehlhorn" title="Kurt Mehlhorn">Kurt Mehlhorn</a> (1999). "An analysis of the highest-level selection rule in the preflow-push max-flow algorithm". Information Processing Letters. 69 (5): 239–242. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.8563">10.1.1.42.8563</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0020-0190%2899%2900019-8">10.1016/S0020-0190(99)00019-8</a>.</cite></li>

<li><cite id="CITEREFDaniel_D._Sleator_and_Robert_E._Tarjan1983" class="citation journal cs1"><a href="Daniel_D._Sleator" class="mw-redirect" title="Daniel D. Sleator">Daniel D. Sleator</a> and <a href="Robert_E._Tarjan" class="mw-redirect" title="Robert E. Tarjan">Robert E. Tarjan</a> (1983). <a rel="nofollow" class="external text" href="https://www.cs.cmu.edu/~sleator/papers/dynamic-trees.pdf">"A data structure for dynamic trees"</a> (PDF). Journal of Computer and System Sciences. 26 (3): 362–391. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0022-0000%2883%2990006-5">10.1016/0022-0000(83)90006-5</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0022-0000">0022-0000</a>.</cite></li>

<li><cite id="CITEREFEugene_Lawler2001" class="citation book cs1"><a href="Eugene_Lawler" title="Eugene Lawler">Eugene Lawler</a> (2001). "4. Network Flows". Combinatorial Optimization: Networks and Matroids. Dover. pp. 109–177. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-486-41453-9</bdi>.</cite></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-12" href="https://en.wikipedia.org/wiki/?title=Maximum_flow_problem&oldid=1300099657">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>